#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#include <math.h>

#define TYPE double
#define NUM_THREADS 2

//  this test checks to make sure that the parallel algorithm 
//  outputs the same results as the sequential.

// the use must define this function to use genericScan
//void userBinaryOperator( void *x1, void *x2) {
//	TYPE *a = (TYPE *) x1;
//	TYPE *b = (TYPE *) x2;
//	
//	*a += *b;
//}

void seqScan(TYPE *X, unsigned int n, unsigned int offset, unsigned int stride);

void tweakedScan(TYPE *X, int n);

void tweakedScanBitOps(TYPE *X, int n);

void hybridScan(TYPE *X, int n, int blockBits);
void hybridScan2(TYPE *X, int n, int blockBits);


// DRIVER
int main( int argc, char **argv) {	
	
	// problem setup
	int n = 10000000;
	int dim = 1;
	int i;
	int m;

	if(argc > 1) 
		n = atoi(argv[1]);

	if(argc > 2) 
		dim = atoi(argv[2]);
		
	TYPE *x = (TYPE *) malloc( sizeof(TYPE) * n);
	TYPE *y = (TYPE *) malloc( sizeof(TYPE) * n);
	
	for (m = 1; m < n; m*= 3) {
	
	for(i = 0; i < m; i++)
		x[i] = i % 2;


/*
	// print input
	printf("Input array:\n");
	for(i = 0; i < n; i++) 
		printf("%.0f ", x[i]); 	
	printf("\n");
*/

	//omp_set_nested(1);
	//omp_set_dynamic(1);

	// scan with timing 
	double t1 = omp_get_wtime(); 
	seqScan(x, m, 0, 1);
	double t2 = omp_get_wtime();

	// gold standard.
	
/*
	//print output
	printf("Output array:\n");	
	for(i = 0; i < n; i++) 
		printf("%.0f ", x[i]); 	
	printf("\n");
*/
	printf("\nseq scan Took %g secs for %d keys\n", t2-t1, m);

	
	for(i = 0; i < m; i++)
		y[i] = i % 2;
/*
	// print input
	printf("Input array:\n");
	for(i = 0; i < n; i++) 
		printf("%.0f ", x[i]); 	
	printf("\n");
*/

	//omp_set_nested(1);
	//omp_set_dynamic(1);

	// scan with timing
	t1 = omp_get_wtime(); 
	tweakedScan(y, m);
	t2 = omp_get_wtime();

	
/*
	//print output
	printf("Output array:\n");	
	for(i = 0; i < n; i++) 
		printf("%.0f ", x[i]); 	
	printf("\n");
*/
	printf("\n\ttweaked scan Took %g secs for %d keys\n", t2-t1, m);
	// compare x and y.
	for (i = 0; i < m; i++) {
		if (x[i] != y[i]) {
			printf("error with results!");
			break;
		}
	}

	
	for(i = 0; i < m; i++)
		y[i] = i % 2;

/*
	// print input
	printf("Input array:\n");
	for(i = 0; i < n; i++) 
		printf("%.0f ", x[i]); 	
	printf("\n");
*/

	//omp_set_nested(1);
	//omp_set_dynamic(1);

	// scan with timing
	t1 = omp_get_wtime(); 
	tweakedScanBitOps(y, m);
	t2 = omp_get_wtime();

	
	
/*
	//print output
	printf("Output array:\n");	
	for(i = 0; i < n; i++) 
		printf("%.0f ", x[i]); 	
	printf("\n");
*/
	printf("\n\tbit scan Took %g secs for %d keys\n", t2-t1, m);
	// compare x and y.
	for (i = 0; i < m; i++) {
		if (x[i] != y[i]) {
			printf("error with results!");
			break;
		}
	}


	for(i = 0; i < m; i++)
		y[i] = i % 2;

/*
	// print input
	printf("Input array:\n");
	for(i = 0; i < n; i++) 
		printf("%.0f ", x[i]); 	
	printf("\n");
*/

	//omp_set_nested(1);
	//omp_set_dynamic(1);

	// scan with timing
	t1 = omp_get_wtime(); 
	hybridScan(y, m, 13);
	t2 = omp_get_wtime();

	
	
/*
	//print output
	printf("Output array:\n");	
	for(i = 0; i < n; i++) 
		printf("%.0f ", y[i]); 	
	printf("\n");
*/
	printf("\n\thybrid scan Took %g secs for %d keys\n", t2-t1, m);
	// compare x and y.
	for (i = 0; i < m; i++) {
		if (x[i] != y[i]) {
			printf("error with results! at %d\n", i);
			printf("truth = %e\n", x[i]);
			printf("computed = %e\n", y[i]);
			break;
		}
	}

	for(i = 0; i < m; i++)
		y[i] = i % 2;

/*
	// print input
	printf("Input array:\n");
	for(i = 0; i < n; i++) 
		printf("%.0f ", x[i]); 	
	printf("\n");
*/

	//omp_set_nested(1);
	//omp_set_dynamic(1);

	// scan with timing
	t1 = omp_get_wtime(); 
	hybridScan2(y, m, 13);
	t2 = omp_get_wtime();

	
	
/*
	//print output
	printf("Output array:\n");	
	for(i = 0; i < n; i++) 
		printf("%.0f ", x[i]); 	
	printf("\n");
*/
	printf("\n\thybrid scan 2 Took %g secs for %d keys\n", t2-t1, m);
	// compare x and y.
	for (i = 0; i < m; i++) {
		if (x[i] != y[i]) {
			printf("error with results! at %d\n", i);
			printf("truth = %e\n", x[i]);
			printf("computed = %e\n", y[i]);
			break;
		}
	}
}
	
	// clean up
	free(x);
	free(y);
	return 0;
}
	




	


	



